import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: qian
 * Date: 2022-07-12
 * Time: 17:50
 */
//创建大根堆
public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }

    /**
     * 建大堆的时间复杂度是O(n)
     * @param array
     */
    public void createHeap(int[] array){
        for(int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            this.usedSize++;
        }
        for(int p=(usedSize-1-1)/2;p>=0;p--){
            shiftDown(p,this.usedSize);
        }
    }

    /**
     *
     * @param root 每颗子树根节点的下标
     * @param len 每颗子树调整结束的条件
     * 向下调整的时间复杂度：O(logn)  -  二叉树的高度
     */
    public void shiftDown(int root,int len){
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            if(child+1<len && this.elem[child]<this.elem[child+1]){
                child++;
            }
            //child一直保存的是孩子的最大值
            if(this.elem[parent]<this.elem[child]){
                int temp=this.elem[parent];
                this.elem[parent]=this.elem[child];
                this.elem[child]=temp;
                parent=child;//开始更新下标,继续向下调整
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

    /**
     * 入队（插入）
     * 仍然要保持大根堆
     * @param val
     */
    public void push(int val){
        if(full()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize++]=val;
        shiftUp(usedSize-1);
    }
    public boolean full(){
        return this.usedSize==this.elem.length;
    }
    /**
     * 向上调整
     * @param child
     */
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(this.elem[child]>this.elem[parent]){
                int temp=this.elem[child];
                this.elem[child]=this.elem[parent];
                this.elem[parent]=temp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

    /**
     * 出队（删除），每次删除的都是优先级高的元素
     * 仍然要保持大根堆
     * @return
     */
    public int pollHeap(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int top=this.elem[0];
        int temp=this.elem[0];
        this.elem[0]=this.elem[usedSize-1];
        this.elem[usedSize-1]=temp;
        usedSize--;
        shiftDown(0,this.usedSize);
        return top;
    }
    public boolean isEmpty(){
        return this.usedSize==0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap(){
        if(isEmpty()){
            return -1;
        }
        return this.elem[0];
    }

    /**
     * 堆排序 - 升序
     * 升序键大堆，降序建小堆
     * @param
     */
    public void heapSort(){
        //createHeap(arr);
        int end=this.usedSize-1;
        while(end>=0){
            int temp=elem[0];
            elem[0]=elem[end];
            elem[end]=temp;
            shiftDown(0,end);
            end--;
        }
    }
}
